//
// Created by Administrator on 2022/2/4.
//

#ifndef CPP_LEARNING_LEETCODE124_H
#define CPP_LEARNING_LEETCODE124_H
#include "treenode.h"
#include <vector>
#include <iostream>
using namespace std;
class Solution124 {

public:
    int maxPathSumVal = INT32_MIN;
    // 以root为顶点的路径的最值
    // 返回 以root为顶点的一条路径的最值
    // 但是要计算 以root为中点的左右路径的最值
    int maxPathSumHelper(TreeNode* root) {
        if(root == nullptr) return 0;
        int leftPathSum = maxPathSumHelper(root->left);
        int rightPathSum = maxPathSumHelper(root->right);

        int pathSum = root->val;
        if(leftPathSum > 0) pathSum += leftPathSum;
        if(rightPathSum > 0) pathSum += rightPathSum;
        maxPathSumVal = max(maxPathSumVal, pathSum);

        int maxOnePath = max(leftPathSum, rightPathSum);

        return  (maxOnePath > 0)  ? root->val + maxOnePath : root->val;
    }
    int maxPathSum(TreeNode* root) {
        maxPathSumHelper(root);
        return maxPathSumVal;
    }
};

void test124(){
    TreeNode node_10(-10);
    TreeNode node9(9);
    TreeNode node20(20);
    TreeNode node15(15);
    TreeNode node7(7);
    node_10.left = & node9;
    node_10.right = & node20;

    node20.right = &node7;
    node20.left = &node15;

    Solution124 s;
    int sum = s.maxPathSum(&node_10);

    cout<<sum<<endl;

}
#endif //CPP_LEARNING_LEETCODE124_H
